package top.retain;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author ivorfan
 * @date 2021/9/7 16:42
 */
public class LFU {

    public static void main(String[] args) {
        LFU lfu = new LFU(2);
        lfu.put(1,1);
        lfu.put(2,2);
        lfu.get(1);
        lfu.put(3,3);
        lfu.get(2);
        lfu.get(3);
        lfu.put(4,4);
        lfu.get(1);
        lfu.get(3);
        lfu.get(4);
    }
    int size = 0;
    int capacity = 0;
    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
    Map<Integer, Integer> map = new HashMap<>();
    public LFU(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            int value = map.get(key);
            getAndIncrement(key);
            return value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.put(key, value);
            getAndIncrement(key);
        } else {
            map.put(key,value);
            size++;
            if (size > capacity) {
                removeLess();
            }
            heap.offer(new int[]{key, 1});

        }
    }


    public void removeLess() {
        int[] entry = heap.poll();
        map.remove(entry[0]);
        size--;
    }

    public void getAndIncrement(int key) {

        Iterator<int[]> it = heap.iterator();
        while (it.hasNext()) {
            int[] next = it.next();
            if (next[0] == key) {
                next[1]++;
                heap.remove(next);
                heap.offer(next);
                break;
            }
        }
    }
}
